package com.mzy.linear_struct.subject;

import javax.lang.model.element.VariableElement;
import java.util.*;

/**
 * @Author: codermzy
 * @Date: 2024/04/27/下午4:05
 * @Description:
 */
public class 斐波那契126 {

    // F(0) = 0，F(1) = 1
    // F(n) = F(n - 1) + F(n - 2)，其中 n > 1


    // 直接递归存在大量重复性计算
    /*
              5
         3         4
      1     2   2     3
                    1   2
     */

    // 解决方案：使用记忆化搜索
    public static int fib(int n) {
        // f0  f1  f2    f3      f4
        // 0   1   1    f1+f2   f3 + f2
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }

        return fib(n - 1) + fib(n - 2);
    }

    // 使用记忆化搜索 斐波那契
    private final static Map<Integer, Integer> memo = new HashMap<>();

    public static int fib1(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        if (memo.get(n) != null) {
            return memo.get(n);
        }
        int sum = fib1(n - 1) + fib1(n - 2);
        memo.put(n, sum);
        return memo.get(n);
    }

    public static long fib2(int n) {

        for (int i = 0; i <= n; i++) {
            if (i == 0) {
                memo.put(i, 0);
                continue;
            }
            if (i == 1) {
                memo.put(i, 1);
                continue;
            }
            int sum = memo.get(i - 1) + memo.get(i - 2);
            memo.put(i, sum);
        }
        System.out.println(memo);
        return memo.get(n);
    }

    public static void main(String[] args) {
        System.out.println(fib1(50));
        System.out.println(fib2(50));
    }
}
